package q992_subarraysWithKDistinct;

public class Solution {
    /*
    此题也是前缀和的一种题型
    首先 对于求出所谓子数组中不同整数的个数恰好为 k 的情况
    我们一般都化解为 子数组中不同整数个数不超过k 和 不超过k-1的两种情况
    二者相减 就能够得到我们所需要的答案
     */
    public int subarraysWithKDistinct(int[] nums, int k) {
        return countK(nums, k) - countK(nums, k - 1);
    }

    /*
    而对于求解不超过k的情况：
    题目中已经给出了 nums数组中所有元素的范围是[0, nums.length]
    所以可以用一个数组来代替hashMap的作用用来记录每个数字出现了多少次
    然后使用 滑动窗口的方法
    temp代表当前窗口内出现了多少种数字 res为答案 l是左指针 而迭代的i就是右指针

     */
    private int countK(int[] nums, int k) {
        int[] counts = new int[nums.length + 1];
        int temp = 0, res = 0, l = 0;
        for (int i = 0; i < nums.length; i++) {
            // 如果当前数字没有出现 则temp++ 代表多了一种数字
            if (counts[nums[i]] == 0) temp++;
            // 然后无论该数字有没有出现过 必然需要counts[nums[i]]++;
            counts[nums[i]]++;
            // 判断 当种类超过k的时候 就需要从左侧指针开始判断并减少窗口内的数字种类
            while (temp > k) {
                // 首先最左侧的对应数字减少
                counts[nums[l]]--;
                // 如果当一个数字出现次数归零 则可以减少种类了
                if (counts[nums[l]] == 0) temp--;
                // 否则左指针还要移动
                l++;
            }
            // res需要加对应的窗口长度 因为是子数组 所以可以出现重复的 例如[1, 1]可以包括两个[1] 和 一个[1, 1]
            res += i - l + 1;
        }

        return res;
    }
}
